package algocasts;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class P66_PascalsTriangle {
    // Time: O(n^2)  Space: O(1)
    public List<List<Integer>> generate(int n) {
        List<List<Integer>> res = new ArrayList<>();
        if (n < 1) return res;
        for (int i = 0; i < n; i++) {
            List<Integer> list = Arrays.asList(new Integer[i + 1]);
            list.set(0, 1);
            list.set(i, 1);
            for (int j = 1; j < i; j++) {
                list.set(j, res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
            }
            res.add(list);
        }
        return res;
    }
}
